package nowcoder;

import java.util.ArrayList;
import java.util.List;

/**
 * @author wangxi created on 2021/5/30 23:46
 * @version v1.0
 *
 * https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
 *
 * 描述
 * 编号为 11 到 nn 的 nn 个人围成一圈。从编号为 11 的人开始报数，报到 mm 的人离开。
 * 下一个人继续从 11 开始报数。
 * n-1n−1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？
 *
 * 约瑟夫环问题
 * 直接使用链表方式解吧， 数学方式太难理解了。。
 */

public class YSF {


    public int ysf (int n, int m) {
        // write code here
        if (n <= 0 || m <= 0) {
            return 0;
        }
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            list.add(i);
        }
        int index = 0;
        while (list.size() > 1) {
            int i = (index + m - 1) % list.size();
            list.remove(i);
            // 此时数据已经整体前移一位了，因此下轮开始的index就是当前位置。
            index = i;
        }
        return list.get(0);
    }
}
